//牛客 OR36 链表的回文结构
//思路：1.先找到中间结点
//2.从中间结点开始往后的所有结点逆置
//3.对比逆置后的链表与原链表mid前所有的val值

#include <stdlib.h>
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
struct ListNode* middleNode(struct ListNode* head)
{
    struct ListNode* fast = head, * slow = head;

    while (fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}
struct ListNode* reverse(struct ListNode* head)
{
    struct ListNode* prev = NULL, * cur = head, * next = NULL;

    while (cur)
    {
        //尾插
        next = cur->next;
        cur->next = prev;
        prev = cur;
        //迭代
        cur = next;
    }
    return prev;
}
class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        // write code here
        struct ListNode* mid = middleNode(A);
        struct ListNode* rmid = reverse(mid);

        while (rmid)
        {
            if (rmid->val != A->val)
                return false;
            rmid = rmid->next;
            A = A->next;
        }
        return true;
    }
};